import java.util.PriorityQueue;
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-09-25
 * Time: 21:36
 */

public class Test2 {
    //leetcode 重排序链表
    public void reorderList(ListNode head) {
        if(head == null || head.next == null) return;
        ListNode hhead = head;
        //1.先找到链表的中间节点
        ListNode slow = head, fast = head,prev = head;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        //2.翻转后半部分链表
        fast = null;
        while(slow != null) {
            ListNode next = slow.next;
            slow.next = fast;
            fast = slow;
            slow = next;
        }
        slow = fast;
        ListNode cur = hhead;
        while(cur != null && slow != null) {
            ListNode nextCur = cur.next;
            ListNode nextSlow = slow.next;
            if(nextCur != null) slow.next = nextCur;
            cur.next = slow;
            cur = nextCur;
            slow = nextSlow;
        }
    }

    //leetcode 合并k个升序链表（方法1）—— 使用优先级队列 时间复杂度O(nklogk)
    public ListNode mergeKLists(ListNode[] lists) {
        //1.创建一个小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1,v2) -> v1.val - v2.val);
        //2.将每个链表的头结点添加进堆中
        for(ListNode l : lists) {
            if(l != null) {
                heap.offer(l);
            }
        }
        //3.合并链表
        ListNode ret = new ListNode();
        ListNode cur = ret;
        while(!heap.isEmpty()) {
            ListNode tmp = heap.poll();
            cur.next = tmp;
            cur = cur.next;
            if(tmp.next != null) heap.offer(tmp.next);
        }

        return ret.next;
    }

    //leetcode 合并k个升序链表（方法2）—— 归并，时间复杂度O(nklogk)
    public ListNode mergeKLists1(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if(left > right) return null;
        if(left == right) return lists[left];

        int mid = left + (right - left) / 2;

        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);

        //合并两个链表
        return mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode head = new ListNode();
        ListNode cur1 = l1, cur2 = l2, cur = head;
        while(cur1 != null && cur2 != null) {
            if(cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
            }else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        if(cur1 != null) cur.next = cur1;
        if(cur2 != null) cur.next = cur2;

        return head.next;
    }
}
